package list_reverse;

import java.util.List;

public class 反转链表_206_92 {
}

class 反转链表_206{
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        // 拿到整个链表的尾巴节点  作为头
        ListNode tailAsHead = reverseList(head.next);
        // 本层两个节点反转  上边那行就是 head.next == null提前返回了  最后一个节点不会走到这里
        head.next.next = head;
        //  避免成环  不然 回到第一个节点的时候 会出现  第一二个节点间为环 也可简化成 注释的写法
        head.next = null;
        return tailAsHead;

        // 以下为迭代双指针法
        //if(head == null || head.next == null) return head;
        //ListNode fst = head;
        //ListNode snd = fst.next;
        //while(snd != null) {
        //    ListNode tmp = snd.next;
        //    snd.next = fst;
        //    fst = snd;
        //    snd = tmp;
        //}
        //head.next = null;
        //return fst;
    }

   /* public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummyHead = head;
        head = reverse(head);
        dummyHead.next = null;
        return head;
    }

    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        // 拿到整个链表的尾巴节点  作为头
        ListNode tailAsHead = reverseList(head.next);
        // 本层两个节点反转  上边那行就是 head.next == null提前返回了  最后一个节点不会走到这里
        head.next.next = head;

        return tailAsHead;
    }*/
}

class 反转链表II_92{
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        reverseBetween(node1, 2,4);
    }
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        // 迭代法较简单  切片出来中间部分 用206的题解答即可
        // 这里用头插法实现
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        // left 的前驱节点 pre 移动到left - 1 的位置
        // 如 pre = -1 到  left = 3 的pre = 2 只要  3 -1 = 2步
        // ListNode pre = head ；  这种会产生 如果left = 1的时候
        // pre.next 就不是第一个节点了 因此要用dummyHead
        ListNode pre = dummyHead;
        for(int i = 1; i<= left - 1 ; i++) {
            pre = pre.next;
        }
        // 双指针  需要搬到片段头部的节点
        // leftNode 代表左边的边界节点  该节点不移动 直到所有的节点都搬到它前面  反转完成
        ListNode leftNode = pre.next;
        ListNode next;
        // 如left = 3  right = 5  需要把45 搬到3前面   因此是 < right
        for(int i = left;i< right ; i++) {
            next = leftNode.next;
            leftNode.next = leftNode.next.next;
            // 插入到dummyLeft前边
            next.next =  pre.next;
            pre.next = next;
        }
        return dummyHead.next;
    }
}


class K个一组翻转链表_25{

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        reverseKGroupO1(node1, 3);
    }
    /**
     * 普通解法
     */
    public static ListNode reverseKGroupO1(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode hair = new ListNode(-1);
        hair.next = head;
        // 保留一个前置  用于迭代
        // 保存 前后节点  pre是前置  nextHead 是下一个head
        ListNode pre = hair;
        while (head != null) {
            ListNode tail = pre;
            for(int i = 0; i< k ; i++) {
                tail = tail.next;
                // 长度不够了 直接返回把
                if(tail == null )
                    return hair.next;
            }
            ListNode nextHead = tail.next;
            ListNode[] reverse = reverseO1(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 拼回去
            pre.next = head;
            tail.next = nextHead;
            // 移动到下一个pre 和 head
            pre = tail;
            head = nextHead;
        }
        return hair.next;
    }

    /**
     * 反转head到tail
     */
    private static ListNode[] reverseO1(ListNode head, ListNode tail) {
        ListNode nextHead = tail.next;
        ListNode next = head.next;
        tail = head;
        // 重点 *** 头指针置空 否则乱序了
        head.next = null;
        while (next != nextHead) {
            // 保存第三个节点
            ListNode nextnext = next.next;
            // 反转到head的节点
            next.next = head;
            // head 和next  后移
            //head.next = null;
            head = next;

            next = nextnext;
        }
        // head 移动到了tail
        return new ListNode[]{head, tail};
    }


    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode nextKGroupHead = head;
        // 每k个用reverse方法  刚好执行了k次 next  tail 是下一个开始
        for(int i = 0; i< k; i++) {
            // 不够移动k次  把头节点返回
            if(nextKGroupHead == null) return head;
            nextKGroupHead = nextKGroupHead.next;
        }
        ListNode newHead = reverse(head, nextKGroupHead);
        // head 是反转之后的尾巴节点
        head.next = reverseKGroup(nextKGroupHead, k);

        return newHead;
    }

    /**
     * 左开右闭
     */
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next  = head.next;
        while (head != tail) {
            next = head.next;
            // 反向往前指
            head.next = pre;
            // pre & head 都向后移动
            pre = head;
            head = next;
        }
        // 刚好最后一个 pre 和head之间  因为head == tail了  没有反转 tail当作后k个的头部
        // 返回第k个
        return pre;
    }
}



class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }